Search results for "Hidden subgroup problem"
showing 2 items of 2 documents
A note on easy and efficient computation of full abelian periods of a word
2016
Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.
Quantum Dual Adversary for Hidden Subgroups and Beyond
2019
An explicit quantum dual adversary for the S-isomorphism problem is constructed. As a consequence, this gives an alternative proof that the query complexity of the dihedral hidden subgroup problem is polynomial.